|
| |
|
|
Ant colony
Hart, Pavel ; Hynčica, Ondřej (referee) ; Honzík, Petr (advisor)
First part of the thesis is about literature research of optimization algorithms. Three of the algorithms were implemented and tested, concretely the ant colony algorithm, tabu search and simulated annealing. All three algorithms were implemented to solve the traveling salesman problem. In second part of the thesis the algorithms were tested and compared. In last part the influence of the ant colony parameters was evaluated.
|
|
|
Large-Scale Travelling Salesman Problem
Kukula, Lukáš ; Žaloudek, Luděk (referee) ; Bartoš, Pavel (advisor)
Thesis deals with solving large-scale traveling salesman problem. The aim is to find the best possible solution within a short time. Most widely used heuristics was compared and most efficient proved to be Lin-Kernighan. This heuristic combined with the stochastic algorithm brings even better results than the Lin-Kernighan heuristic itself.
|
|
|
Traveling Salesman Problem: Parallel Methods Using SMP (Threads)
Weigner, Martin ; Jaroš, Jiří (referee) ; Kašpárek, Tomáš (advisor)
This thesis is focused on solving the problem of traveling salesman. At first, the problem is solved by serial access at four algorithms. There are two of them chosen and transferred to parallel access. In the end there are summarized observations about different parameters of both access. This thesis also introduces questions of programming parallel applications with threads to the reader.
|
|
|
Graph Coloring
Procházka, Lukáš ; Goldefus, Filip (referee) ; Masopust, Tomáš (advisor)
This thesis is about graph coloring, which is assigning colors to vertices of a graph such that no two vertices, which are linked with an edge, have the same color. This problem is very computational hard, because it's NP-complete. It's also very important, because it has many practical applications. Here are described some of the heuristic algorithms, which try to solve this problem by iteratively improving the initial solution with given number of colors. Three of them have been implemented, tested on different graphs and compared considering several criteria.
|
|
|
Evolutionary Optimization of Tour Timetables
Filák, Jakub ; Bidlo, Michal (referee) ; Jaroš, Jiří (advisor)
This thesis deals with the problem of vehicle scheduling in public transport. It contains a theoretical introduction to vehicles scheduling and evolutionary algorithms. Vehicle scheduling is analyzed with respect to the bus timetables. Analysis of evolutionary algorithms is done with emphasis on the genetic algorithms and tabu-search method After the theoretical introduction, a memetic algorithm for the given problem is analyzed. Finally, the thesis contains a description of the optimization system implementation and discusses the experiments with the system.
|
|
|
Information System for a School Including Automated Timetabling
Švadlenka, Jiří ; Jurka, Pavel (referee) ; Chmelař, Petr (advisor)
This thesis devote itself to use of information system for school agenda administration. Schools are forced to administer big amounts of informations, not only referred to their students. Broad issue is very extensive and disparate, so the most common types of data and demands on school information system operation are stated. The system for automatic generation of timetables is part of the school information system. At the first, basic conceptions of scheduling scope are defined and tied together with them are methods and algorithms for timetable creation problem solving. School timetabling is problem of scheduling lessons with certain limitative conditions. Further, thesis is engaged in design of school information system, data organization in such system and solving of system design problems. Designed information system accentuates on easy expandability and wide range of usage possibilities. Also suggested algorithm for solving of defined school timetabling is stated in this part of thesis.
|
|
| |
|
|
Large-Scale Travelling Salesman Problem
Kukula, Lukáš ; Žaloudek, Luděk (referee) ; Bartoš, Pavel (advisor)
Thesis deals with solving large-scale traveling salesman problem. The aim is to find the best possible solution within a short time. Most widely used heuristics was compared and most efficient proved to be Lin-Kernighan. This heuristic combined with the stochastic algorithm brings even better results than the Lin-Kernighan heuristic itself.
|
|
|
Vehicle Routing Problem
Kafka, Ondřej ; Branda, Martin (advisor) ; Hanzák, Tomáš (referee)
The thesis deals with optimization problems which arise at distribution planning. These problems can often be easily formulated as integer programming problems, but rarely can be solved using mixed integer programming techniques. Therefore, it is necessary to study the efficiency of heuristic algorithms. The main focus of the thesis is on the vehicle routing problem with time windows. A tabu search algorithm for this problem was developed and implemented. It uses integer programming to solve the set partitioning problem in order to find optimal distribution of all customers into feasible routes found during the search. The results of the classical integer programming approach, basic insertion heuristic and presented tabu search algorithm are compared in a numerical study.
|
guest ::
